# -*- coding: utf-8 -*-

"""剑指 Offer II 107. 矩阵中的距离
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。 

示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0
"""

class Solution:
    """本体一开始想用动态规划，然后细想出现问题，这是不是线性规划强调的无后效性？
    两个相邻点A，B；A距0的最近距离，为 min(其四周另外三点与B距0的最短距离)；
    那么在计算B的最近的距离时，因为A与其相邻，又需要计算出A的最近距离，这不就卡bug了吗？死循环
    
    那么无论如何都是可以用回溯的方法的，每个点，都回溯一遍，得出结果，只是成本有点高。
    
    仔细观察这道题，有点像等高线，比喻成海平面一步步升高。
    扫描一次，先把为0的点作为基本海平面，高度为0，得到一个基本的海陆分布图（矩阵）
    扫描这个海陆分布图，海平面升高1，将沿海的陆地淹没一层，更新海陆图；
    再扫描一次海陆分布图，海平面升高1，将沿海的陆地淹没一层， 更新海陆图；
    ...
    直到所有的陆地全被淹没。
    
    客观地讲，需要扫描的次数是最高陆地的高度。
    
    这道题提交结果时间和空间在python中都超过90%，可见算法并没有固定的一招一式，有时候换个角度考虑未尝不可。"""
    def updateMatrix(self, mat: list) -> list:
        length, size = len(mat), len(mat[0])
        total, count = length*size, 0

        height = 0
        i = 0
        while i < length:
            j = 0
            while j < size:
                if mat[i][j] == 1:
                    mat[i][j] = float('inf')
                else:
                    count += 1
                j += 1
            i += 1

        while count < total:
            next_height = height + 1
            i = 0
            while i < length:
                j = 0
                while j < size:
                    if mat[i][j] == height:
                        if j-1 > -1 and mat[i][j-1] > next_height:
                            mat[i][j-1] = next_height
                            count += 1
                        if j+1 < size and mat[i][j+1] > next_height:
                            mat[i][j+1] = next_height
                            count += 1
                        if i-1 > -1 and mat[i-1][j] > next_height:
                            mat[i-1][j] = next_height
                            count += 1
                        if i+1 < length and mat[i+1][j] > next_height:
                            mat[i+1][j] = next_height
                            count += 1
                    j += 1
                i += 1

            height = next_height

        return mat

if __name__ == '__main__':
    print(Solution().updateMatrix([[0,1,0,1,1],[1,1,0,0,1],[0,0,0,1,0],[1,0,1,1,1],[1,0,0,0,1]]))
